Learning outcomes

This is how I intend to study the midterms by checking against learning objective. I should be able to understand the concept and fulfill the learning objective.

The first level checkbox is the learning objective, which is checked if I understand. The second bullet point is supplementary information that I have added. Content in bold are content that I may be unsure of.

Introduction

Machine Learning

• Define machine learning in terms of algorithms, tasks, performance and experience.

  • algorithms that improve their performance at some task with experience

• State that the goal of machine learning is generalization.

  • generalises well even on unseen data.

• List three main types of machine learning, e.g. supervised, unsupervised, and reinforcement learning.

• Describe some potential dangers in machine learning, e.g. making unethical predictions due to bias in training data, undesirable feedback between machine and human learning, applying an algorithm without understanding its assumptions.

Learning Frameworks

Pipeline

• List the steps in the machine learning pipeline: collect data, extract features, design models, train models, select models, evaluate solution.

• Define the roles of training, validation and test data in the pipeline, and describe their structure as sets of pairs of inputs/features and targets.

• Define the following: model, estimator, model parameter, training objective, optimal parameter, optimal estimator.

  • Each model (a set of linear functions) is a set of estimators (a linear function) consisting of paramters (coefficients).

• Explain the difference between training and prediction.

• Explain the difference between underfitting and overfitting.

• Give an example in regression of a task, the performance evaluation (via test data), the given experience (via training data), and the training algorithm.

Decision Theory

• Define and give examples of action, loss, risk, empirical risk and decision.

  • Actions - Objects considered in decision making

  • Loss - Amount lost by action based on truth .

    • "Minimising the empirical risk under squared loss is the same as maximising the likelihood under Gaussian error"
    • where

  • Risk - Expected loss given true distribution which is unknown.

  • Emprirical Risk - Estimated risk given data (which can be training data validation data or test data )

  • Decision Action chosen based on data

• Give examples of different kinds of loss functions.

  • squared loss (L2), absolute loss (L1), zero-one loss (L0), negative log-likelihood

• Define the inability to generalize as risk, and explain why we need to estimate this risk with empirical risk, e.g. training, validation, test errors.

  • Inability of to generalise = bias + variance + noise
  • 

Optimization

• Describe how to derive exact solutions or use gradient descent for optimization problems. Describe how local minima problems can be mitigated.

  • Local minima problem - solve for all local minima for exact solution, multiple starting points for gradient descent

• Explain why we may prefer descent over exact methods in machine learning.

  • Faster and feasible computation, transferable algorithms

• Outline some computational strategies for machine learning: distributed computation, stochastic gradient descent, automatic differentiation.

• Compute gradients automatically using PyTorch.

  • xxxxxxxxxx
    optimizer.zero_grad()
    outModel = model(data)
    loss = criterion(outModel, target)
    loss.backward()
    optimizer.step()
    

Regression

• Define regression statistically as estimating the conditional expectation of an unknown target given the observed inputs.

  • To obtain estimator .

• Outline the statistical methodology in regression: learn the conditional distribution using maximum likelihood; derive the conditional expectation.

  • Learn conditional distribution with maximum likelihood.
  • Derive the conditional expectation from .

• Given a conditional distribution and data set, write down the (conditional) likelihood, the negative log-likelihood and derive its gradient.

  • 
  • How to derive the gradient?

• Describe a generalized linear model as a set of conditional distributions (from some exponential family) with a link function. View linear regression as a GLM.

  • conditional distribution from some exponential family
  • link function (does this need to be invertible?)

• List strategies to overcome overfitting in models with many parameters.

  • More data, less parameters, early stopping, model selection

Model Selection

• Explain in words the bias-variance tradeoff, and how it affects model selection.

  • Inability of to generalise = bias + variance + noise

Regularization

• Explain that regularization helps generalization by creating for model selection, a family of models where model complexity is penalized to different extents during training. Describe how the hyperparameters are selected.

  • Different regulraisation parameter for to penalise the complexity of the model to different extents.
  • Hyperparameters are selected with validation error.

• Describe the difference between the training objective and the training error.

  • training objective = training error + regularisation

• Give examples of regularizers that are commonly used in machine learning.

  • Ridge regression
  • Lasso regression
  • Lasso has higher test error, picks a simpler model, and runs faster for subset selection.

• Explain how the exact solution for ridge regression stabilizes the estimator.

  • No longer a problem when there are more parameters than data

• Explain how gradient descent for ridge regression works through shrinkage.

  • The parameter shrinks at every step, unless propped by the gradient.
  • 

Classification

• Describe the difference between classification and regression.

  • The target is a label instead of a real value.

• Given a perceptron, draw its decision boundary and decision regions.

  • , is one if positive, zero otherwise.
  • is orthogonal to the decision boundar which splits the space into decision regions
  • Gradient is zero almost anywhere.

Logistic Regression

• Write down the model in logistic regression, and describe how a classifier can be derived from a conditional distribution in the model after learning.

• Write down logistic regression as a generalized linear model. Derive the training objective and the training gradient.

  • Conditional distribution

    • From the Bernoulli family

  • Link function

  • Training objective is to minimise negative log likelihood

  • Training gradient is the average of point gradients

    • Point gradient

Softmax Regression

• Define one-hot encodings for labels in multiclass classification.

  • Logistic regression is the case when the number of labels is two.

• Write down the model in softmax regression. Define the softmax function. Explain why the last column of the matrix of parameters may be set to zero.

  • Model vector of probabilities
  • Dimensions of parameter
  • As adding a constant to any entire row does not change the model, the last column may be subtracted from every column without changing the model, the last column may be set to zero.

• Write down softmax regression as a generalized linear model

  • Conditional distribution

    • From the Bernoulli family

  • Link function

    • What is ? It is any constant such that the sum of probabilities become one?

  • Training objective is to minimise negative log likelihood

    • Point loss

  • Training gradient is the average of point gradients

    • Point gradient

Neural Networks

Feedforward Networks

• Define an artificial neuron. Give examples of activation functions.

  • sigmoid , tanh , softplus , ReLU

• Write down forward propagation in matrix notation.

  • 

• Distinguish between network parameters and network architecture.

  • Weights and biases versus arrangement and number of neurons and activation functions used

• Give examples of network architectures in supervised learning (e.g. convolutional networks) and in unsupervised learning (e.g. autoencoders).

  • Undersupervised learning and "reduced representation"

Backpropagation

• Define the training loss and the backpropagated error. Derive the gradients in terms of the backpropagated error using chain rule.

  • 
  • 

• Outline the steps of the backpropagation algorithm. Explain how dynamic programming speeds up the computation of the gradient during training.

  • 

• Explain why deep learning is more successful today than it was in the 1980s.

  • Too little data, computers too slow, weights initialised wrongly, wrong type of non-linearity (should use ReLU instead of sigmoid which saturates)

Feature Engineering

• Explain the success of deep learning in terms of removing the need for handcrafted features by domain experts.

  • The features learnt in each layer are learnt by backprop, not designed by hand. The weights learnt in the neural network are called feature maps.

• Give examples of applications of deep learning.

• View a deep network with ReLU activations as a piecewise-linear function.

  • Piecewise linear functions can approximate function.
  • Deep network is a model of piecewise linear functions. How are the regions derived?
  • regions with neurons to fit any shape in the data.

• Explain the strengths and the limitations of deep learning using the universal approximation theorem and the no-free-lunch theorem.

  • Universal approximation theorem - there exist two-layer neural network (with arbtirarily large middle layer) perform perfectly on training data - but will overfit
  • No-free-lunch theroem - if an algorithm performs well on a certain class of problems, it has degraded performance on the remaining problems - not all problems are useful however

• Describe how deep learning enables regression/classification with less data by learning lower dimensional structure in high dimensional data

  • Data is often near low-dimensional manifold in a high dimensional space - Sparsity aids the learning low-dimensional manifold - Fewer labeled points needed for classification

• Describe how deep learning advances machine learning (software without explicit programming) by allowing modular blocks to be chained and trained.

  • Differentiable programming - "search to a continuous subset of the program space" - "assembling networks of parameterized functional blocks" - you can chain together different blocks and train them together - and this is how deep learning is different from traditional machine learning

Convolutional Networks

• Explain how convolution of shared filters and pooling of feature maps solves the dimensionality problem in computer vision.

  • A fully connect layer requires too many parameters - The location feature in an image does not matter, "translation invariance, feature invariance"

• Compute the tensor convolution of a multichannel feature map by multichannel filters. Define the kernel size, stride and padding in a convolution.

  • Please know how to compute by hand

• Identify the purpose of different blocks in a given piece of PyTorch code.

Recurrent Neural Networks

• Distinguish between feedforward and recurrent networks.

• Describe how recurrent networks learn long-term dependencies in sequential data by storing temporal states and accessing them with attention.

  • • Matrix of keys , vector of values , vector of query
    • How much to select , What to select
    • could be a sigmoid or softmax
    • is the notation for element-wise product
    • Returns a vector

• Describe attention mechanisms in terms of queries on key-value pairs.

  • Input for every cell

    • cell state
    • concatenate of output state and input vector

  • Output for every cell

    • cell state
    • output state

  • Update cell state

    • Selective forget

  • - What to forget (A kind of attention) - Key matrix , Query vector - Outputs a 0-to-1 vector - Applied on previous state to forget

    • Selective remember

      • • What to remember (A kind of attention)
        • Key matrix , Query vector
        • Outputs a 0-to-1 vector

      • • How much to remember (A kind of attention)

    • Key matrix . Query vector

    • Outputs a -1-to-1 vector

    • is added to the cell state.

  • Selective output

Kernel Methods

Maximum Margins

• Explain how the problem of finding a classifier with maximal margin widths can be written as a constrained squared-loss optimization problem.

• Explain why soft margins are needed for linearly inseparable data, and how it can be written as a constrained optimization problem with slack variables.

  • minimise
  • subject to and

• Explain how the hinge loss classifier with regularization is the same as the soft margin classifier with slack variables.

  • minimise

• Analyze the effects (in terms of margin width and in terms of generalization) of changing the hyperparameters or on the trained classifier.

Duality

Comment: As the two strategies are explained side-by-side, it was quite hard to follow. Moreover you are mixing primal-dual (from optimsation) and Lagrangian (from systems world).

• Outline two strategies (dual problem with box constraints, exact solution to KKT conditions) for solving optimization problems with inequality constraints.

  • Solve a dual optimisation problem where the constraints are nicer and where it is easier to implement gradient descent.

    • Box constraints (variable ) are easier to work with, and the objective function is still manageable (quadratic for example).

  • Solve the Lagrangian system of equations.

    • Write down the Lagrangian, solve for critical points, pick the critical point which gives the global minimum. Issue - manipulating math may be hard (?).

• Write down the primal and dual problems in terms of the Lagrangian. Compare the primal and dual optimal values using the max-min inequality.

  • Lagrangian
  • Objective of primal player - minimise Approach - set all to zero and you get
  • Objective of dual player - maximise Approach - for each compute . Return the maxmin.
  • Intuition - you do better if you have the final say.

• Given a constrained optimization problem, derive the dual problem and its constraints, and write down the complementary slackness conditions.

  • This uses both the primal and dual formulations.

    

  • The Lagrangian, primal inequalities , dual inequalities and complelementary slackness.

    

Support Vector Machines

• Outline how the dual form of a support vector machine may be derived from the primal form with slack variables (but no need to memorize the dual form).

  • 
  • 
  • 
  • 

• Define support vectors as feature vectors linearly combined in the optimal . Recognize that often, there are only a few support vectors.

  • 

• Describe how the value of the multiplier determines the position of a feature vector 𝑥 in relation to the margin of the classifier.

  • 

• Write down the formula of the resulting classifier in terms of the support vectors, and its offset in terms of a boundary support vector.

  • is a support vector, is the new data. Non-support vectors are not in the classifier because its is zero
  • 

Kernels

• Describe the kernel trick as a strategy to reduce computation during training and prediction by writing them in terms of an easy-to-compute kernel as opposed to a difficult-to-compute feature map. Illustrate this with an example.

  • Refer to Polynomial and Radial Basis Kernel

• Define a kernel as a symmetric function which generates Gram matrices that are positive semidefinite. Relate kernels to similarity maps and distance maps.

  • for all

  • for all

    • The Gram matrix is positive semidefinite

  • symmetric (previous property)

  • all eigenvalues are nonnegative (not imaginary)

  • Existence of a feature map function

    • However may be hard to find.

  • When is large, and is similar (and the distance is small)

• Write down the linear, polynomial and radial basis kernels.

  • Linear Kernel

  • Polynomical kernel

    • For ,

  • Radial Basis Kernel

    • returns an infinite dimensional vector

Kernelization

• Describe how to use a radial basis kernel in an SVM for training and prediction.

  • Refer to SVM, but should be

• Outline how a representation of as a linear combination of feature vectors can be used to derive the kernel ridge regression.

  • SVM is a classifier, kernels can be used for regression.
  • will be a linear combination of vectors .
  • You can use other kernels instead of the linear kernel.
  • 
  • 

• Describe the pros and cons of using a higher-order kernel (e.g. radial basis kernel or polynomial kernel of high order) for classification or regression.

  • Underfitting and overfitting (will not generalise well to unseen data).

Graphical Models

Probability

• Define the multinomial and multivariate Gaussian distributions. Recognize in the Gaussian distribution as the covariance matrix.

• Write down the resulting multivariate Gaussian distribution after applying a change of basis to a spherical Gaussian distribution.

• Define the conditional independence of and given .

  • for all outcomes and and .

Graph Theory

• Identify the following aspects of a graph: vertex, edge, undirected graph, directed graph, adjacent, child, parent, descendent, ancestor, path, cycle, directed path, undirected path, collider, non-collider.

  • parent child
  • ancestor child something descendant
  • a variable is a collider when it is causally influenced by two or more variables

• Identify the following kinds of graphs: acyclic directed graph, complete graph, subgraph, clique, maximal clique.

  • clique - a complete subgraph
  • maximal clique - a clique not contained in any larger clique

• Define the separation of sets and by . Define the d-separation of sets and by .

  • 
  • 
  • Non-colliders are open (can pass through, connects), but closed if in
  • Colliders are usually closed, but open if in or its desendants is in
  • 
  • Is and d-separated (given anything other set)?

• Define a graphical model as a collection of random variables with a graph defining the relationship between the variables. Recognize shaded and unshaded nodes as observed and hidden variables respectively.

• Recognize directed edges as descriptions of conditional distributions. Recognize undirected edges as descriptions of joint distributions. Define Bayesian networks and Markov random fields.

Bayesian Networks (Directed Graphical Models)

• Define a distribution satisfying the factorization property with respect to a graph using conditional distributions.

• Describe ways to define multinomial distributions and Gaussian distributions which factorize with respect to a graph. Given a graph, write down the inverse covariance of the corresponding Gaussian using linear dependencies.

  • 

• Define the global Markov property of a distribution with respect to a graph. Determine if a statement is true using d-separation.

  • A distribution satisfies the global Markov property with respect to graph if

    • for all the disjoint sets ,, that and are d-separated given

  • and is conditionally independent given i.e.

• Understand the Hammersley-Clifford Theorem as stating the equivalence between two ways of defining Bayesian networks.

  • satisifies the factorisation property with respect to
  • satisifies the global Markov property with respect to

• Understand the concept of explaining away, that conditioning on a collider will lead to dependence between two parent variables.

  • Knowing the battery is flat explains away the observation that the gauge level is zero (there is less need to consider another explanation). Fuel level is less likely to be zero even though battery level does not affect fuel level.

Markov Random Fields (Undirected Graphical Models)

• Define a distribution satisfying the factorization property with respect to a graph using potential functions. If the distribution is strictly positive, give the definition in terms of energy functions.

  • We say satisfies the factorisation property with respect to if for some nonnegative potentials where
  • If the nonnegative potential functions are positive, we can write for some energy function . Then

• Define the global Markov property in terms of separation.

  • A distribution satisifies the global Markov property with respect to graph if

    • for all disjoint subsets ,, that and are separated given .

  • and are conditionally indepedent given , i.e.

  • How did the class example satisfy this?

• Define the pairwise Markov property in terms of non-adjacency.

  • We say that a distribution satisfies the pairwise Markov property with respect to if for all non-adjacent variables and ,
  • This is a special case of global Markov property, where the two conditionally independent sets have one element each, and are not adjacent.
  • Isn't this like all the simple graphs? - Seems like you need to property to draw the graph that way.

• Understand the Hammersley-Clifford Theorem as stating the equivalence between three ways of defining strictly positive Markov random fields.

  • If is strictly positive, then the following are equivalent.

  • satisifies the factorisation property with respect to

  • satisifies the global Markov property with respect to

  • satisifies the pairwise Markov property with respect to

    • Two variables that are not adjacent are independent of each other if conditioned on every other variable, because the covariance matrix of the two matrix will be a diagonal.

• Describe ways to define multinomial distributions and Gaussian distributions which factorize with respect to a graph.

  • 

• Given a graph, write down the inverse covariance of the corresponding Gaussian using the pairwise Markov property.

  • 

• Recognize a Boltzmann machine as a special case of a multinomial distribution with binary variables and only two-way interactions (second-order energies).

  • What is a Boltzmann machine? What does it do?
  • "only two-way interactions" - All higher-order energies can be written in terms of second-order ones.
  • With all the second order energies (each of them is a matrix), we can write the weights in terms of the second order energies.
  • We can write the joint distribution of the entire Boltzmann machine as well.